const tree = require('./tree');

const zOrderTraverseNode = (root) => {
	if (root == null) {
		return root;
	}
	let flag = false;
	const res = [];
	let children = [];
	let grandchildren = [];
	children.push(root);
	while (children.length > 0) {
		let current;

		if (flag) {
			current = children.shift();
			res.push(current.val);
			if (current.left) {
				grandchildren.push(current.left);
			}
			if (current.right) {
				grandchildren.push(current.right);
			}
		} else {
			current = children.pop();
			res.push(current.val);
			if (current.right) {
				grandchildren.unshift(current.right);
			}
			if (current.left) {
				grandchildren.unshift(current.left);
			}
		}
		
		if (children.length === 0 && grandchildren.length !== 0) {
			children = children.concat(grandchildren);
			grandchildren = [];
			flag = !flag;
		}
	}
	return res;
}

const zOrderTraverseResult = zOrderTraverseNode(tree);

console.log(zOrderTraverseResult); // [ 11, 7, 15, 20, 13, 9, 5, 3, 8, 10, 12, 14, 18, 25 ]
